COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a34.tex[154,phy] \today\hfill}
\parskip 6pt

\bigskip
\line{\bf Ogden's Pumping $uvwxy$ Theorem\hfill}

Let $G$ be a CFG with terminal alphabet $T=T↓1+T↓0$. Let the weight of
a character be~1 if in~$T↓1$, 0~if in $T↓0$; the weight of a string is
the total weight of its terminal characters. In a derivation tree, define
a weight and a weight-branching height for each node by these rules:

\smallskip
\disleft 20pt:(1):
$N$ is a leaf node, labeled with a member of $T↓1$. Then $h(N)=0$,
$w(N)=1$.

\smallskip
\disleft 20pt:(2):
$N$ is a leaf node, not labeled with a member of $T↓1$. Then $h(N)=w(N)=0$.

\smallskip
\disleft 20pt:(3):
$N$ has sons $N↓1,N↓2,\ldots,N↓k$, with weights $w↓1,\ldots,w↓k$ and
heights $h↓1,\ldots,h↓k$. Let ${\rm wt}(N)=w↓1+w↓2+\cdots +w↓k$. If $w(N)=w↓i$
for some~$i$, $h(N)=h↓i$. Otherwise $h(N)=1+\max↓i h↓i$.

\smallskip
One proves by induction on size of subtree:

\smallskip
\disleft 20pt:(A):
The weight of a node is the weight of its yield.

\smallskip
\disleft 20pt:(B):
A node of weight 0 has height 0.

\smallskip
\disleft 20pt:(C):
A node of height $h$ has in its yield a nested set of $h$~phrases, all
of different weights.

\smallskip
\disleft 20pt:(D):
If $l$ is the length of the longest RHS in~$G$, at each node $w≤l↑h$.

\smallskip
If a sentence has weight $w>l↑g$, where $g$ is the number of variables
in~$g$, and height~$h$, then $l↑h≥w>l↑g$, $h≥g+1$, there is a node of
height $g+1$, with a properly nested set of $g+1$ phrases in its yield.
Two of them must be derived from the same variable~$A$:

$$\vcenter{\halign{$\ctr{#}$\qquad&$\ctr{#}$\qquad
&$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$\cr
&&S\cr
\noalign{\bigskip\bigskip}
&&A\cr
\noalign{\bigskip}
&&A\cr
\noalign{\bigskip\bigskip}
u&v&w&x&y\cr}}$$

\bigskip
\noindent The larger phrase, $vwx$, has weight $≤l↑{g+1}$. Because of
proper nesting, $vx$~has weight $≥1$.
Then we have $S\aRa uAy$, $A\aRa vAx$, $A\aRa w$, $\fnc{wt}(vx)>0$, 
$\fnc{length}(vx)>0$. Then for each $i≥0$, $S\aRa uAy\aRa uv↑iAx↑iy
\aRa uv↑iwx↑iy$, where $w$, $vwx$, $v↑2wx↑2$, etc., are phrases in the
derivation of $uv↑iwx↑iy$.

\vfill\eject

Letting $n=l↑{g+1}$, we conclude:

\proclaim Ogden's Theorem. For every weighted context-free language~$L$,
there is an $n>0$, and for every sentence~$z$ with ${\rm wt}(z)≥n$ there is
a decomposition $z=uvwxy$, such that $\{\,uv↑iwx↑iy\mid i≥0\,\}⊂L$,
${\rm wt}(vx)≥1$, ${\rm wt}(vwx)≤n$.

Letting $T↓1=T$, $T↓0=\emptyset$, we get as a corollary the

\proclaim Pumping Theorem. For every context-free language $L$, there is an
$n>0$, and for every sentence~$z$ with $|z|≥n$ there is a decomposition
$z=uvwxy$, such that $\{\,uv↑iwx↑iy\mid i≥0\,\}⊂L$, $|vx|≥1$,
$|vwx|≤n$.

Summing up, informally: any sentence that is long enough, in a CFL, is
pumpable, up and down. Any large enough subset of the characters of a
sentence may be involved in the pumping. The characters of weight one
need not belong to a separate alphabet; the proof works no matter how
the heavy leaves are chosen.

\smallskip
\line{\bf Example.\hfill}

Prove $\{\,a↑ib↑jc↑k\mid i≤j≤k\,\}$ is not a CFL. If it were, let
$T↓1=\{a\}$, $T↓0=\{b,c\}$, and apply the lemma to $a↑nb↑nc↑n$ for
sufficiently large~$n$.

$$\vcenter{\offinterlineskip
\halign{\vrule#&\strut\quad$\hfil#\hfil$\quad&\vrule#&\quad$\hfil#\hfil$\quad%
&\vrule#&\quad$\hfil#\hfil$\quad&\vrule#\cr
\noalign{\hrule}
height4pt&\omit&&\omit&&\omit&\cr
&a↑n&&b↑n&&c↑n&\cr
height4pt&\omit&&\omit&&\omit&\cr
\noalign{\hrule}
}}$$

\noindent
Clearly $v$ and $x$ must each belong to one of $a↑{\ast}$, $b↑{\ast}$, 
or~$c↑{\ast}$,
and one of them must belong to~$a↑+$. Then $uv↑2wx↑2y$ must have
more than $n\;a$'s, but exactly $n\;b$'s or exactly $n\;c$'s, contradiction.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft November 20, 1984

\bye